/*
 * @lc app=leetcode.cn id=5 lang=typescript
 *
 * [5] 最长回文子串
 */

// @lc code=start
function longestPalindrome(s: string): string {
  // 解决串长度偶数问题，统一变成奇数处理
  const getManacherStr = (s: string): string => {
    let ns = '#';
    for (let c of s) {
      ns += c + '#';
    }
    return ns;
  };

  let ns = getManacherStr(s);
  const n = ns.length;
  // 当前点为中心的最长半径
  const dist = new Array(n).fill(0);
  // 记录第一个回文的区间，r会不断被更大的回文长度更新
  let l = 0;
  let r = -1;
  for (let i = 0; i < n; i++) {
    if (i > r) {
      dist[i] = 1;
    } else {
      dist[i] = Math.min(r - i, dist[l + r - i]);
    }
    // 以当前值为中心找回文串
    while (i - dist[i] >= 0 && ns[i - dist[i]] === ns[i + dist[i]]) {
      dist[i]++;
    }
    // 更新最大回文串区间
    if (i + dist[i] > r && i - dist[i] > 0) {
      r = i + dist[i];
      l = i - dist[i];
    }
  }
  // 找到所有的回文区间，把最长的回文串计算出来
  let ans: string;
  let max = -1;
  for (let i = 0; i < dist.length; i++) {
    if (max > dist[i]) continue;
    // 找出最长的dist，计算字符串
    max = dist[i];
    ans = '';
    for (let j = i - dist[i] + 1; j < i + dist[i]; j++) {
      if (ns[j] === '#') continue;
      ans += ns[j];
    }
  }
  return ans;
}
// @lc code=end
